# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/5 17:10 
"""
"""

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 

示例 1：


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：


输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def print(self):
        """
        默认以层次遍历打印该二叉树
        Returns:

        """
        stack=[self]
        while stack:
            temp=stack.pop(0)
            print(temp.val,end="\t")
            if temp.left:
                stack.append(temp.left)
            if temp.right:
                stack.append(temp.right)

class Solution:
    def sortedArrayToBST(self, nums) :
        """
        将有序数组转换成二叉搜索树
        Args:
            nums:

        Returns:

        """
        mid = len(nums) // 2
        print('mid:',mid)
        root = TreeNode(nums[mid])
        if mid == 0 :  # 叶结点
            return root
        # root.left = self.sortedArrayToBST(nums[:mid])
        # root.right = self.sortedArrayToBST(nums[mid + 1:])
        root.left,root.right=map(self.sortedArrayToBST,[nums[:mid],nums[mid:]])
        return root


if __name__=="__main__":
    nums=[-10, -3, 0, 5, 9]
    S=Solution()
    tmp=S.sortedArrayToBST(nums)
    tmp.print()






